package com.algrithom.tree.binarytree;

import java.util.Objects;

import com.common.model.TreeNode;
import com.util.TreeOperUtil;

public class Solution14 {
    
    public static void main(String[] args){
        Integer[] A = new Integer[]{1,2,3};
        Integer[] B = new Integer[]{3,1};
        Solution14 solution14 = new Solution14();
        TreeNode<Integer> treeA = TreeOperUtil.createTree(A,0);
        TreeNode<Integer> treeB = TreeOperUtil.createTree(B,0);
        System.out.println(solution14.isSubStructure(treeA,treeB));
    }
    
    public boolean isSubStructure(TreeNode<Integer> A,TreeNode<Integer> B){
        if (Objects.isNull(A) || Objects.isNull(B)) {
            return Boolean.FALSE;
        }
        return recur(A,B) || isSubStructure(A.getLeftChild(),B) || isSubStructure(A.getRightChild(),B);
    }
    
    private boolean recur(TreeNode<Integer> nodeA,TreeNode<Integer> nodeB){
        if (Objects.isNull(nodeB)) {
            return Boolean.TRUE;
        }
        if (Objects.isNull(nodeA) && !nodeA.getValue().equals(nodeB.getValue())) {
            return Boolean.FALSE;
        }
        return recur(nodeA.getLeftChild(),nodeB.getLeftChild()) && recur(nodeA.getRightChild(),nodeB.getRightChild());
    }
}
